package nextGreaterElement;

import java.util.*;

public class Solution {
    static class Node{
        int index;
        int value;
        public Node(int index,int value){
            this.index = index;
            this.value = value;
        }
    }
//    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
//
//        Node[]nodes = new Node[nums2.length];
//        for (int i = 0; i < nodes.length; i++) {
//            nodes[i] = new Node(i,nums2[i]);
//        }
//        Arrays.sort(nodes, (o1, o2) -> o1.value-o2.value);
//        for (int i = 0; i < nums1.length; i++) {
//            int index = find(nums1[i],nodes);
//            if(index!=-1){
//                nums1[i] = findFirstBigger(index,nums2);
//            }else{
//                nums1[i] = -1;
//            }
//        }
//        return nums1;
//    }
//    private int find(int target,Node[]nodes){
//        // 查找相同的元素 二分查找
//        int res = -1;
//        int l = 0,r = nodes.length-1;
//        // 左闭右闭 [r,l]
//        while(l<=r){
//            int mid = l + (r-l)/2;
//            if(nodes[mid].value<target){
//                l = mid+1;
//            }else if(nodes[mid].value>target){
//                r = mid-1;
//            }else {
//                return nodes[mid].index;
//            }
//        }
//        return -1;
//    }
//    private int findFirstBigger(int index,int[]nums){
//        for (int i = index+1; i < nums.length; i++) {
//            if(nums[i]>nums[index]){
//                return nums[i];
//            }
//        }
//        return -1;
//    }

    //单调栈解法
    public int[] nextGreaterElement(int[] nums1, int[] nums2) {
        // 找到nums1中的下一个更大的元素
        Map<Integer,Integer> map = findBigger(nums2);
        int[] ans = new int[nums1.length];
        for (int i = 0; i < nums1.length; i++) {
            if(map.containsKey(nums1[i])){
                ans[i] = map.get(nums1[i]);
            }else {
                ans[i] = -1;
            }
        }
        return ans;
    }
    private Map<Integer,Integer> findBigger(int[] nums){
        Map<Integer,Integer> map = new HashMap<>();
        Stack<Integer> stack = new Stack<>();
        for (int i = 0; i < nums.length; i++) {
            while(!stack.isEmpty()&&nums[stack.peek()]<nums[i]){
                map.put(nums[stack.pop()],nums[i]);
            }
            stack.push(i);
        }
        return map;
    }

}
